Corelab Seminar
2010-2011
Charis Agelidakis
Approximation algorithms for 2-Stage Stochastic Optimization Problems
Abstract.
Stochastic Optimization attempts to model uncertainty in the input data.
More specifically, it studies decision making when only probabilistic information about the input is given, and not the actual input data.
The concept of having to make decisions under uncertainty about future requirements rises naturally in many areas, including transporation models,
logistics, financial instruments and network design. In such cases, while more effective decisions can be made when the actual requirements are given,
the decision-making costs are inflated until then.
In this talk, we will focus on 2-stage stochastic optimization problems. The 2-stage stochastic problem can be stated as follows:
first, given only distributional information about some of the input data, one commits on initial (first-stage) actions, and then,
once the actual data is realized, according to the distribution, further recourse actions, which are costlier, can be taken, so that
one can augment the first-stage solution to satisfy the revealed requirements.
We will present various techniques for approximating 2-stage stochastic variants of well-known combinatorial optimization problems.
A simple framework based on sampling will be presented to obtain constant factor approximation algorithms for a certain class of problems,
as well as an FPRAS for a wide class of stochastic linear programs, based on the ellipsoid method, which can be used, in conjuction with rounding techniques,
to yield constant factor approximation algorithms for various discrete problems. We will finally state that this last result can also be obtained
by utilizing the widely used Sample Average Approximation Method (SAA).